#ifndef _MY_SKIP_LIST_H_
#define _MY_SKIP_LIST_H_

#include <ctime>  
#include <cstring>
#include <cstdio>  

#include <iostream>           
#include <vector>     
#include <queue>     
#include <map>     
#include <algorithm> 
#include <string>
#include <unordered_map>  
#include <memory>   
#include <cmath>
#include <set> 
#include <random>
#include <thread>
using namespace std;

#include "tools.h"

void testSkipTable();

// 自定义的跳表
template<typename K, typename V>
class skiplist
{
private:
	static constexpr int MAX_LEVEL = 16;
	static constexpr double P = 0.6;
	static constexpr time_t DefaultT = 60; // 默认过期时间 60s
	//随机数产生相关, #include<random>，详见cppreference
	std::random_device rd;
	std::mt19937 gen; // 是伪随机数产生器，用于产生高性能的随机数
	std::uniform_real_distribution<> dis; // Produces random floating-point values  x , uniformly distributed on the interval [ a , b )
	struct node
	{
		K key;
		V value; 
		time_t expiresT; // 到期时间
		
		node* next[MAX_LEVEL + 1];
		node() 
		{
			memset(next, 0, sizeof(node*) * ( MAX_LEVEL+1) ); 
		}
		node(K k, V v) :  node(){
			key = k;
			value = v;
			expiresT = myGetTime_t() + DefaultT;
		}
	};
	node *head; // 头节点
public:
	skiplist()
	{
		head = new node; // 头节点
		gen = std::mt19937(rd());
		dis = std::uniform_real_distribution<>(0, 1);
	}
	~skiplist() { 
		while (head != NULL) {
			node *tmp = head->next[1];
			delete head;
			head = tmp;
		}
		cout << "~skiplist" << endl;
	}
	V* find(K x) {  
		node *pre[MAX_LEVEL + 1];
		node *now = head;
		for (int i = MAX_LEVEL; i >= 1; --i) {
			while (now->next[i] != NULL && now->next[i]->key < x) now = now->next[i];
			pre[i] = now;
		}
		// 如果不存在
		if (now->next[1] == NULL || now->next[1]->key != x) return nullptr;
		// 如果超时
		if (now->next[1]->expiresT < myGetTime_t()) {
			// 将前面的连接到后面，然后删除
			node *del = now->next[1];
			for (int i = MAX_LEVEL; i >= 1; --i) {
				if (pre[i]->next != NULL && pre[i]->next[i] == del)
					pre[i]->next[i] = pre[i]->next[i]->next[i];
			}
			delete del;
			return nullptr;
		}
		// 不超时则返回 
		return &(now->next[1]->value); 
	}
	int _randomLevel() {
		int ret = 1;
		while (ret < MAX_LEVEL && dis(gen) < P)  
			++ret; 
		return ret;
	}
	bool insert(K x, V val) {
		
		node *pre[MAX_LEVEL + 1] = {NULL}; //前驱
		node *now = head;
		int level = _randomLevel();
		for (int i = MAX_LEVEL; i >= 1; --i) {
			while (now->next[i] != NULL && now->next[i]->key < x)
				now = now->next[i];
			pre[i] = now; // 每层的
		}
		if (now->next[1] != NULL && now->next[1]->key == x) {
			now->next[1]->value = val;
			time_t timeNow = myGetTime_t() ;
			bool ret=true;
			if( now->next[1]->expiresT >= timeNow )
				ret = false;
			now->next[1]->expiresT = timeNow + DefaultT; // 更新时间
			return ret; // exist
		} 
		node *tmp = new node(x, val); 
		for (int i = level; i >= 1; --i) {
			tmp->next[i] = pre[i]->next[i]; // 在中间插入
			pre[i]->next[i] = tmp;
		}
		return true;
	}

	bool remove(K x) {
		node *pre[MAX_LEVEL + 1];
		node *now = head;
		for (int i = MAX_LEVEL; i >= 1; --i) {
			while (now->next[i] != NULL && now->next[i]->key < x) now = now->next[i];
			pre[i] = now;
		}
		if (now->next[1] == NULL || now->next[1]->key != x) return false;

		// 将前面的连接到后面，然后删除
		node *del = now->next[1];
		for (int i = MAX_LEVEL; i >= 1; --i) {
			if (pre[i]->next != NULL && pre[i]->next[i] == del)
				pre[i]->next[i] = pre[i]->next[i]->next[i];
		}
		delete del;
		return true;
	}
};




#endif // _MY_SKIP_LIST_H_